package com.javabasic.algorithm.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author xiongmin
 * @Description
 * @Date 2021-06-06 20:41
 * @Version 1.0
 **/
public class OnesAndZeroes {


    /**
     * 多维背包问题
     * dp[i][j] 表示至多使用i个0 j个1 能包含的子集中数量最多的个数
     * @param strs
     * @param m
     * @param n
     * @return
     */
    public int findMaxForm3(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        Map<Integer, Integer> onesAndZeroes = null;
        int oneNums = 0;
        int zeroNums = 0;
        for (String str : strs) {
            System.out.println(str);
            onesAndZeroes = getOnesAndZeroes(str);
            oneNums = onesAndZeroes.get(1);
            zeroNums = onesAndZeroes.get(0);
            for (int i = m; i >= zeroNums; i--) {
                for (int j = n; j >= oneNums; j--) {
                    dp[i][j] = Math.max(dp[i][j],dp[i-zeroNums][j-oneNums]+1);
                }
            }
        }
        return dp[m][n];

    }


    public int findMaxForm(String[] strs, int m, int n) {
        int length = strs.length;
        int result = 0;
        int max = getMax(0, strs, length, m, n, 0);
        return Math.max(result, max);
    }

    int result = 0;

    public int findMaxForm2(String[] strs, int m, int n) {
        int length = strs.length;

        getMax2(0, strs, length, m, n, 0);
        return result;
    }

    private void getMax2(int index, String[] strs, int length, int m, int n, int subSize) {
        if (m < 0 || n < 0) {
            result = Math.max(subSize - 1, result);
            return;
        }
        if (index >= length) {
            result = Math.max(subSize, result);
            return;
        }
        Map<Integer, Integer> onesAndZeroes = getOnesAndZeroes(strs[index]);
        /**
         * 要当前的字符串
         */
        getMax2(index + 1, strs, length, m - onesAndZeroes.get(0), n - onesAndZeroes.get(1), subSize + 1);
        /**
         * 不要当前的字符串
         */
        getMax2(index + 1, strs, length, m, n, subSize);

    }

    private int getMax(int index, String[] strs, int length, int m, int n, int subSize) {
        if (m < 0 || n < 0) {
            return subSize - 1;
        }
        if (index >= length) {
            return subSize;
        }
        Map<Integer, Integer> onesAndZeroes = getOnesAndZeroes(strs[index]);
        /**
         * 要当前的字符串
         */
        int max1 = getMax(index + 1, strs, length, m - onesAndZeroes.get(0), n - onesAndZeroes.get(1), subSize + 1);
        /**
         * 不要当前的字符串
         */
        int max2 = getMax(index + 1, strs, length, m, n, subSize);
        return Math.max(max1, max2);

    }

    private Map<Integer, Integer> getOnesAndZeroes(String str) {
        HashMap<Integer, Integer> onesAndZeroes = new HashMap<>();
        onesAndZeroes.put(0, 0);
        onesAndZeroes.put(1, 0);
        if (str == null || str.isEmpty()) {
            return onesAndZeroes;
        } else {
            int length = str.length();
            Integer one, zero;
            for (int i = 0; i < length; i++) {
                if (str.charAt(i) == '0') {
                    zero = onesAndZeroes.get(0);
                    onesAndZeroes.put(0, zero + 1);
                } else if (str.charAt(i) == '1') {
                    one = onesAndZeroes.get(1);
                    onesAndZeroes.put(1, one + 1);
                }
            }
        }
        return onesAndZeroes;
    }
}
